#pragma once 

#include "Common.h"
#include "Cache.h"


// whether to log AB search
// #define LOG_AB
// AB Log Id
extern int g_ABLogId;

//#define LOG_CACHE

#define GAME_TIMEOUT			0xFFFFFF
#define VALUE_TT_MOVE			1000000

#define MAX_MOVES				500
#define MAX_DEPTH				99
#define HISTORY_DEPTH_LIMIT		3

template<typename BB> int NegamaxBB(int depth, BB *bb, bool bWhite, BB* pbbMove = NULL );

 // Move Sorting
////////////////////////////////////////////////////////////////////////////////

template<typename BB>
void MoveQuickSort(BB** moveList, int left, int right)
{
	BB * tmp;
	if(left < right)
	{
		int boundary = left;
		for(int i = left + 1; i < right; i++)
		{
			if(moveList[i]->score > moveList[left]->score)
			{
				++boundary;
				tmp = moveList[i];
				moveList[i] = moveList[boundary];
				moveList[boundary] = tmp;
			}
		}
		tmp = moveList[left];
		moveList[left] = moveList[boundary];
		moveList[boundary] = tmp;

		MoveQuickSort(moveList, left, boundary);
		MoveQuickSort(moveList, boundary+1, right);
	}
}

 // QuiescenceSearch - evaluation to the "calm" position
////////////////////////////////////////////////////////////////////////////////////////////////////////

template<typename BB>
int QuiescenceSearch(SEngineData* ed, BB* bb, ZOBRIST_KEY zkeyBoard, bool bWhite, int alpha, int beta, int depth = 0)
{
	// check the time
	if(CheckTime(ed))
		return GAME_TIMEOUT;

	// increase number of nodes
	ed->iNumberOfNodes++;

	// check, if we have to make capture
	if(TestJump<BB>(ed, bb, bWhite) == false) 		
	{
		// no capture, return evaluation

		// calculate and set depth
		int calmDepth = ed->dwMaxDepth + abs(depth);
		if(calmDepth > ed->iReachedCalmPosDepth)
			ed->iReachedCalmPosDepth = calmDepth;
	
		if(ed->bUseEndGameDB) // if we can use EGTB Probing
		{
			// check draw by repetition
			if(IsDrawByRepetition(ed, zkeyBoard))
				return 0;

			// TO-DO: fill int constants
			const int BitsPerRow = 4;
			const int MaxField = 31;
			uint8 dtm;
			int eval = ed->pReader->Lookup<BB, BitsPerRow, MaxField>(bb, bWhite ? WHITE : BLACK, &dtm);

			// convert value
			switch(eval)
			{
			case WIN:
				return GAME_WIN - dtm - calmDepth;
			case LOSS:
				return GAME_LOSS + dtm + calmDepth;
			case DRAW:
				return 0;
			}		
		}

		// return evaluation in the "calm" position
		return Evaluation<BB>(ed, bb, bWhite);
	}
	else
	{
		// go deeper till there are no captures

		// check draw by repetition
		if(IsDrawByRepetition(ed, zkeyBoard))
			return 0;

		// generate captures
		BB bitMove[MAX_MOVES];
		int moveCount = MoveGenerator<BB>(ed, bb, bWhite, bitMove);
		if(moveCount == 0)
			return GAME_LOSS;

		// iterate through captures
		for(int i = 0; i < moveCount; i++)
		{
			// do move
			ToggleMove<BB>(bb, &bitMove[i]);
			ZOBRIST_KEY zkeyMove = GenerateZobristHash<BB>(&bitMove[i], bWhite);
			zkeyBoard ^= zkeyMove;
			DrawPushMove(ed, zkeyBoard);

			// call deeper
			int value = -QuiescenceSearch(ed, bb, zkeyBoard, !bWhite, -beta, -alpha, depth - 1);

			// undo move
			DrawPopMove(ed, zkeyBoard);	
			zkeyBoard ^= zkeyMove;
			ToggleMove<BB>(bb, &bitMove[i]);

			// check alpha and beta-cutoff
			if(value > alpha || i == 0)
			{
				alpha = value;

				if(value > beta)
				{
					return value;
				}
			}

		}

		return alpha;
	}
}


 // BitBoard NegaMax
////////////////////////////////////////////////////////////////////////////////////////////////////////

template<typename BB> int NegamaxBB(SEngineData* ed, int depth, BB *bb, bool bWhite, BB* pbbMove )
{
	// if at the minimal level, evaluate the leaf
	if(depth == 0)
	{
		return QuiescenceSearch<BB>(ed, bb, 0, bWhite, GAME_LOSS, GAME_WIN);
	}

	ed->iNumberOfNodes++;

	// generate bitboard moves
	BB bitMoves[MAX_MOVES];
	int moveCount = MoveGenerator<BB>(ed, bb, bWhite, bitMoves);
	if(moveCount == 0)
		return GAME_LOSS;

	// iterate through moves
	BitBoardMove bbBestMove;
	int bestResult = GAME_LOSS - 1;
	for(int i = 0; i < moveCount; i++)
	{
		ToggleMove<BB>(bb, &bitMoves[i]);

		// call next level
		int result = -NegamaxBB<BB>(ed, depth - 1, bb, ! bWhite, NULL );

		ToggleMove<BB>(bb, &bitMoves[i]);

		// compare result
		if(result >= bestResult)
		{
			memcpy(&bbBestMove, &bitMoves[i], sizeof(BB));
			bestResult = result;
		} // if

	} // for

	if(pbbMove)
		memcpy(pbbMove, &bbBestMove, sizeof(BB));

	return bestResult;
}


 // BitBoard AlfaBeta
////////////////////////////////////////////////////////////////////////////////////////////////////////

template<typename BB>
int AlphaBetaDeep(SEngineData* ed, int depth, int nestedLevel, BB *bb, bool bWhite,  int alpha, int beta, 
				  ZOBRIST_KEY zkeyBoard, BB* pbbMove = NULL, bool bPVS = false, bool bIsPV = false)
{
	// if at the minimal level, evaluate the leaf
	if(depth == 0)
	{
		return QuiescenceSearch<BB>(ed, bb, zkeyBoard, bWhite, alpha, beta);
	}

	ed->iNumberOfNodes++;

	// check the time
	if(CheckTime(ed))
		return GAME_TIMEOUT;

	// probe TT cache
	int cacheValue = 0;
	int cacheAlpha = alpha;
	int cacheBeta = beta;
	uint8 cacheHashF = 0;
	BB bbTTMove;
	memset(&bbTTMove, 0, sizeof(bbTTMove));
	if(Cache_Lookup<BB>(ed, zkeyBoard, depth, nestedLevel, cacheHashF, cacheValue, alpha, beta, bWhite, &bbTTMove) == true)
	{
		return cacheValue;
	}

	// TT cut-off????
	if(alpha >= beta)
		return alpha;

	// test TT move
	ZOBRIST_KEY zkeyTTMove = 0;
	if( ! (bbTTMove.wm == 0 && bbTTMove.wm == 0 && bbTTMove.bm == 0 && bbTTMove.bk == 0) )
		zkeyTTMove = GenerateZobristHash<BB>(&bbTTMove, bWhite);

	// check draw by repetition
	if(IsDrawByRepetition(ed, zkeyBoard))
		return 0;

	// generate bitboard moves
	BB bitMoves[MAX_MOVES];
	BB *pBitMove[MAX_MOVES];
	int moveCount = MoveGenerator<BB>(ed, bb, bWhite, bitMoves);
	if(moveCount == 0)
		return GAME_LOSS + (ed->iMaxDepth - depth);

	assert(moveCount < MAX_MOVES);

	// generate move scores for move ordering
	for(int i = 0; i < moveCount; i++)
	{
		pBitMove[i] = &(bitMoves[i]);
		pBitMove[i]->score = 0;
		if(GenerateZobristHash<BB>(pBitMove[i], bWhite) == zkeyTTMove)
			pBitMove[i]->score = VALUE_TT_MOVE;
	}
	
	HistoryUpdateScore<BB>(ed, bb, bitMoves, moveCount, bWhite);
	UpdateKillerScore<BB>(ed, bitMoves, moveCount, bWhite, nestedLevel);

	// log scores BEFORE sorting
#ifdef LOG_AB
	LogMessage(g_ABLogId, "Before sorting:\n");
	LogMessage(g_ABLogId, "--------------\n");
	for(int i = 0; i < moveCount; i++)
	{
		LOG_MSG(g_ABLogId, "%d;", pBitMove[i]->score);
	}
	LogMessage(g_ABLogId, "\n");
#endif

	MoveQuickSort<BB>(pBitMove, 0, moveCount);

	// log scores AFTER sorting
#ifdef LOG_AB
	LogMessage(g_ABLogId, "After sorting:\n");
	LogMessage(g_ABLogId, "--------------\n");
	for(int i = 0; i < moveCount; i++)
	{
		LOG_MSG(g_ABLogId, "%d;", pBitMove[i]->score);
	}
	LogMessage(g_ABLogId, "\n");
#endif

	// iterate through moves
	BB bbBestMove;
	int bestResult = GAME_LOSS - 1; 
	BYTE hashF = hashfALPHA;
	int oldAlpha = alpha;
	bool raised_alpha = false;

	memset(&bbBestMove, 0, sizeof(BB));
	bool bFirstMove = true;

	for(int i = 0; i < moveCount; i++)
	{
		// do move
		ZOBRIST_KEY zkeyMove = GenerateZobristHash<BB>(pBitMove[i], bWhite);

		ToggleMove<BB>(bb, pBitMove[i]);
		zkeyBoard ^= zkeyMove;
		DrawPushMove(ed, zkeyBoard);
	
		int result = 0;

		// switch between PVS and classic AlphaBeta
		if(bPVS)
		{
			// Principal Variation Search
			if( ! bIsPV || depth < 3) //  if low depth or do not do PV search
			{
				result = -AlphaBetaDeep<BB>(ed, depth - 1, nestedLevel + 1, bb, ! bWhite, -beta, -alpha, 
											zkeyBoard, NULL, bPVS, false);					
			}
			else
			{
				if(!raised_alpha) // if not raised alpha - do full window search
				{
					result = -AlphaBetaDeep<BB>(ed, depth - 1, nestedLevel + 1, bb, ! bWhite, -beta, -alpha, 
												zkeyBoard, NULL, bPVS, true);					
				
				}
				else // raised alpha - do zero-window search
				{
					result = -AlphaBetaDeep<BB>(ed, depth - 1, nestedLevel + 1, bb, ! bWhite, -alpha - 1, -alpha, 
												zkeyBoard, NULL, bPVS, false);
					// if better move
					if(result > alpha)
					{
						result = -AlphaBetaDeep<BB>(ed, depth - 1, nestedLevel + 1, bb, ! bWhite, -beta, -alpha, 
												zkeyBoard, NULL, bPVS, true);
					}
				}
			}
		}
		else
		{
			// Normal Alpha-Beta
			result = -AlphaBetaDeep<BB>(ed, depth - 1, nestedLevel + 1, bb, ! bWhite, -beta, -alpha, zkeyBoard);
		}
		
		DrawPopMove(ed, zkeyBoard);	
		zkeyBoard ^= zkeyMove;
		ToggleMove<BB>(bb, pBitMove[i]);


		if(abs(result) == GAME_TIMEOUT)
			return GAME_TIMEOUT;


		// compare result
		if(result > bestResult || (bFirstMove == true && nestedLevel == 1))
		{
			bFirstMove = false;
			bestResult = result;
			memcpy(&bbBestMove, pBitMove[i], sizeof(BB));

			if(result > alpha)
			{
				hashF = hashfVALUE;
				alpha = result;
				raised_alpha = true;
				if(TestJump<BB>(ed, bb, bWhite) == false && depth >= HISTORY_DEPTH_LIMIT)
				{
					IncrementMove<BB>(ed, bb, pBitMove[i], bWhite, depth);
				}
			}
		} // if
		if(result >= beta)
		{
			if(TestJump<BB>(ed, bb, bWhite) == false)
			{
				if(depth < 30 && depth >= HISTORY_DEPTH_LIMIT)
					IncrementMove<BB>(ed, bb, pBitMove[i], bWhite, depth * depth);
				SetKiller(ed, zkeyMove, nestedLevel);
			}
			bestResult = result;
			hashF = hashfBETA;

			break;
		}

	} // for

	// store value to cache
	cacheValue = bestResult;
	//if(hashF == hashfALPHA)
	//	cacheValue =  alpha;
	//else if(hashF == hashfBETA)
	//	cacheValue = beta;
	//else
	//	cacheValue = bestResult;

	//// test zero-window search
	//if(oldAlpha + 1 == beta)
	//	cacheValue = bestResult;

	Cache_Store<BB>(ed, zkeyBoard, depth, nestedLevel, cacheValue, hashF, bWhite, &bbBestMove);

	if(pbbMove)
		memcpy(pbbMove, &bbBestMove, sizeof(BB));

	//return alpha;
	return bestResult;
}

 // MTDf BitBoard Search
////////////////////////////////////////////////////////////////////////////////////////////

template<typename BB>
int MTDf(SEngineData* ed, int depth, int firstGuess, BB *bb, bool bWhite, ZOBRIST_KEY zkeyBoard, int alpha, int beta)
{
	// set the score and bounds
	int score = firstGuess;
	int upperBound = beta;
	int lowerBound = alpha;
	int b = 0;

	// prune by zero-window search
	while(upperBound > lowerBound)
	{
		// set the beta value for zero-window search
		if(score == lowerBound)
			b = score + 1;
		else
			b = score;

		// do the zero-window search
		score = AlphaBetaDeep<BB>(ed, depth, 2, bb, bWhite, b - 1, b, zkeyBoard, NULL);

		// is cut-off
		if(score >= beta)
			return score;

		// check time out
		if(abs(score) == GAME_TIMEOUT)
			return GAME_TIMEOUT;

		// evaluate and shift the bounds
		if(score < b)
			upperBound = score;
		else
			lowerBound = score;
	}

	// return result
	return score;
}

 // Search Root - the top "ply 1" searching function
/////////////////////////////////////////////////////////////////////////////////////////////////

template<typename BB>
int SearchRoot(SEngineData* ed, int depth, int firstGuess, bool bMTDf, bool bPVS, int alpha, int beta, BB *bb, bool bWhite, ZOBRIST_KEY zkeyBoard, BB* pbbMove)
{
	// generate bitboard moves
	BB bitMoves[MAX_MOVES];
	BB *pBitMove[MAX_MOVES];
	int moveCount = MoveGenerator<BB>(ed, bb, bWhite, bitMoves);
	if(moveCount == 0)
		return GAME_LOSS + (ed->iMaxDepth - depth);
	assert(moveCount < MAX_MOVES);

	// update move scores
	for(int i = 0; i < moveCount; i++)
	{
		pBitMove[i] = &(bitMoves[i]);
		pBitMove[i]->score = 0;
	}
	
	HistoryUpdateScore<BB>(ed, bb, bitMoves, moveCount, bWhite);
	UpdateKillerScore<BB>(ed, bitMoves, moveCount, bWhite, 1);

	// sort moves
	MoveQuickSort<BB>(pBitMove, 0, moveCount);

	// pre-move iteration initialization
	BB bbBestMove;
	int bestResult = GAME_LOSS - 1; 
	BYTE hashF = hashfALPHA;

	memset(&bbBestMove, 0, sizeof(BB));
	bool bFirstMove = true;

	// iterate through moves
	for(int i = 0; i < moveCount; i++)
	{
		// do move
		ZOBRIST_KEY zkeyMove = GenerateZobristHash<BB>(pBitMove[i], bWhite);
		ToggleMove<BB>(bb, pBitMove[i]);
		zkeyBoard ^= zkeyMove;
		DrawPushMove(ed, zkeyBoard);
	
		// go deeper for search
		int result = 0;

		// choose between MTDf and ordinary Alpha-Beta
		if(bMTDf)
		{
			result = -MTDf<BB>(ed, depth - 1, -firstGuess, bb, !bWhite, zkeyBoard, -beta, -alpha);
		}
		else
		{
			result = -AlphaBetaDeep<BB>(ed, depth - 1, 2, bb, !bWhite, -beta,  -alpha, zkeyBoard, 
										NULL, bPVS, bPVS);
		}

		// undo move
		DrawPopMove(ed, zkeyBoard);	
		zkeyBoard ^= zkeyMove;
		ToggleMove<BB>(bb, pBitMove[i]);

		// check time-out
		if(abs(result) == GAME_TIMEOUT)
			return GAME_TIMEOUT;

		// evaluate result and alpha-beta window
		if(result > bestResult || bFirstMove == true)
		{
			bFirstMove = false;
			bestResult = result;
			memcpy(&bbBestMove, pBitMove[i], sizeof(BB));

			if(result > alpha)
			{
				hashF = hashfVALUE;
				alpha = result;
				firstGuess = result;
			}
		} // if
		if(result >= beta)
		{
			if(TestJump<BB>(ed, bb, bWhite) == false)
			{
				SetKiller(ed, zkeyMove, 1);
			}
			bestResult = result;
			hashF = hashfBETA;

			break;
		} // if
	} // for

	// store value to cache
	int cacheValue = bestResult;
	//if(hashF == hashfALPHA)
	//	cacheValue =  alpha;
	//else if(hashF == hashfBETA)
	//	cacheValue = beta;
	//else
		//cacheValue = bestResult;

	Cache_Store<BB>(ed, zkeyBoard, depth, 1, cacheValue, hashF, bWhite, &bbBestMove);

	// copy the best move and return result
	if(pbbMove)
		memcpy(pbbMove, &bbBestMove, sizeof(BB));

	return bestResult;
}
	

 // Interative Deepening
/////////////////////////////////////////////////////////////////////////////////////////////////


template<typename BB>
int AlphaBetaBB(SEngineData* ed, BB* bb, bool bWhite, DWORD dwCompTime, BB* pbbMove, long cacheSizeMB, bool bMTDf = false, bool bPVS = false)
{	
	// open AB Log
#ifdef LOG_AB
	g_ABLogId = LogInit("c:\\Log\\ABSearch.log");
#endif

	int bestEvaluation = GAME_LOSS - 1;
	if(bMTDf)
		bestEvaluation = 0;
	ed->iNumberOfNodes = 0;

	ClearHistoryTable(ed);
	ClearDrawRepetition(ed);
	InitKillers(ed);

	// check, if we have only one move
	BB bbMoves[MAX_MOVES];
	if(MoveGenerator<BB>(ed, bb, bWhite, bbMoves) == 1)
	{
		// if there is only one move, exit
		memcpy(pbbMove, &bbMoves[0], sizeof(BB));
		return 0;
	}

	ZOBRIST_KEY zkeyBoard = GenerateZobristHash<BB>(bb, bWhite);

	BB bbMove, bbBestMove;
	memset(&bbBestMove, 0, sizeof(BB));
	memset(&bbMove, 0, sizeof(BB));

	ed->iCacheHit = 0;
	ed->iCacheMiss = 0;

	Cache_Allocate<BB>(ed, ed->iCacheSizeMB);

	// init the timer control
	InitTimeControl(ed, dwCompTime);

	// do first-level probe
	bestEvaluation = SearchRoot<BB>(ed, 1, 0, false, false, GAME_LOSS - 1, GAME_WIN + 1, 
			bb, bWhite, zkeyBoard, &bbMove);


	for(int depth = 2; depth < 99; depth++)
	{
		ed->dwMaxDepth = depth;

		if(GetTickCount() - ed->dwStartTime > dwCompTime)
			break;

		// choose between MTDf and ordinary Alpha-Beta
		int eval = SearchRoot<BB>(ed, depth, bestEvaluation, bMTDf, bPVS, GAME_LOSS - 1, GAME_WIN + 1, 
			bb, bWhite, zkeyBoard, &bbMove);

		// check the best move, is it better?
		if(abs(eval) != GAME_TIMEOUT)
		{
			bestEvaluation = eval;
			memcpy(&bbBestMove, &bbMove, sizeof(BB));
		}
		if(abs(eval) != GAME_TIMEOUT)
		{
			ed->iReachedDepth = depth;
		}
		if(abs(eval) == GAME_TIMEOUT)
			break;
	}

#ifdef LOG_CACHE
	DumpCache(ed);
#endif

	Cache_Free<BB>(ed);

	ed->iNodesPerSec = ed->iNumberOfNodes / (dwCompTime / 1000);

	// close AB log
#ifdef LOG_AB
	LogClose(g_ABLogId);
#endif



	memcpy(pbbMove, &bbBestMove, sizeof(BB));
	return bestEvaluation;
}
